//647 Palindromic Substrings
/*
给定一个字符，求其有多少个回文子字符串。回文的定义是左右对称

输入输出样例
	输入是一个字符串，输出一个整数，表示回文子字符串的数量

Input: "aaa"
Output: 6

六个回文子字符串分别是 ["a","a","a","aa","aa","aaa"]
*/
int countSubstrings(string s) {
	int count = 0;
	for (int i = 0; i < s.length(); ++i) {
		count += extendSubstrings(s, i, i); // 奇数长度
		count += extendSubstrings(s, i, i + 1); // 偶数长度
	}
	return count;
}
int extendSubstrings(string s, int l, int r) {
	int count = 0;
	while (l >= 0 && r < s.length() && s[l] == s[r]) {
		--l;
		++r;
		++count;
	}
	return count;
}